%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Answers for 6.863 Assignment2
% Created by Olga Wichrowska 06/2010
% Modified by rcb 9/1/12
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[10pt]{article}

\setlength{\topmargin}{-0.8in}
\setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.25in}

\usepackage{sectsty}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{subfigure}

\sectionfont{\large}
\subsectionfont{\normalsize}
\subsubsectionfont{\small}

\newcommand{\handout}[3]{
  \renewcommand{\thepage}{#1 - \arabic{page}}
  \noindent
  \begin{center}
    \hspace*{-0.25in}\framebox[6.5in]{
      \vbox{
        \hbox to 6.25in { {\bf 6.863J/9.611J: Natural Language Processing } 
                          \hfill Prof. Robert C. Berwick }
        \vspace{4mm}
        \hbox to 6.25in { {\Large \hfill #1  \hfill} }
        \vspace{2mm}
        \hbox to 6.25in { {\it #2 \hfill #3} }
        }
      }
  \end{center}
  \vspace*{4mm}
}

\begin{document}
\handout{Assignment 2: Context-free grammar writing}{My posse consists of: Ravi Netravali}{Peng Wang}

\begin{enumerate}

\item {\bf Hand in the output of a typical sample run of 10
  sentences from your random sentence generator.  Be sure to attach
  the code so we can test it.}

\begin{itshape}
every fine pickled floor on the chief of staff on every sandwich on every pickle on every delicious fine sandwich on the president on every president with a perplexed delicious chief of staff on every sandwich with a sandwich on the sandwich with a president with a pickle on a pickle on every chief of staff with the perplexed president with a chief of staff on every fine president in every floor wanted every floor in the pickled president .

every sandwich pickled every president in every pickle in every floor in a floor .

is it true that every floor on a pickle pickled the president ?

a chief of staff with a pickle under a pickled floor with every president on the floor in every floor under a chief of staff on the sandwich on every sandwich under the floor on every perplexed sandwich under the floor on every president on every floor in a pickle under the sandwich in the floor with the perplexed pickle in every sandwich under a chief of staff under every pickle under a sandwich in a floor on the floor on a fine chief of staff under a floor under the pickle in the chief of staff in the chief of staff under a sandwich under every delicious president on a pickle under the sandwich in a pickle on every president under a floor on every chief of staff under a pickle with the president on every pickle in every delicious president under the president on every pickle with every pickle with a floor in a pickle in a floor under the floor in the fine pickle in the sandwich under every president on a chief of staff with the president under every sandwich in every chief of staff with the sandwich on every chief of staff under a chief of staff with the fine sandwich on a chief of staff under the fine fine chief of staff under every president in every floor on a pickle with every pickle under the pickled pickle on the fine president with every chief of staff with every president under the sandwich in a sandwich under every sandwich with the chief of staff in every floor with every pickle under the sandwich in a floor with every chief of staff under a pickle under the sandwich on a floor on a sandwich under the sandwich with every chief of staff on the chief of staff in a president in the floor on the pickle with every floor under the chief of staff under a floor with every fine pickle in a pickle on every president with a sandwich under a sandwich under every sandwich under a president with the pickle under a pickle under the chief of staff in the sandwich on a sandwich under a chief of staff with every president on a chief of staff on every floor on the sandwich on every sandwich on every pickle in the president with the pickle under the chief of staff on every floor under a chief of staff in the pickle under a delicious pickle in the pickled floor under a perplexed chief of staff on a chief of staff under every chief of staff with every pickle on a sandwich with every pickled president under a sandwich with the floor with every delicious chief of staff under the floor on a president on a president under the floor under every floor in the pickled delicious floor with every floor under a chief of staff on the chief of staff in the president under a floor in a delicious sandwich with a sandwich with every floor on the delicious sandwich in the sandwich in every perplexed floor in the pickle in every chief of staff under a floor under a floor under a floor with the president on every delicious president with the fine pickle on a president with the fine chief of staff in the floor under a fine chief of staff on every perplexed perplexed sandwich in the floor on a delicious pickle in a president with every pickle in a delicious pickle in a floor in every president with the chief of staff in the president on every pickle on a pickle with the fine president on the sandwich on a chief of staff with a sandwich in the floor under every chief of staff under the president on every sandwich under every chief of staff under every chief of staff under a president with the president in the chief of staff on the sandwich under every pickle in a chief of staff under every president on every floor on every chief of staff with every perplexed fine perplexed floor with the floor under every sandwich in the sandwich under every chief of staff in every chief of staff on every chief of staff in every president in every floor with a pickled floor on every chief of staff under a chief of staff with the president with the sandwich in every sandwich with a fine pickle on the floor under a chief of staff in every floor in every delicious chief of staff under the pickled chief of staff under the chief of staff in a pickle under the president in the floor in a sandwich in a pickle in a pickle on every floor under a floor with a sandwich under every president on every president under every pickle in the chief of staff under every sandwich with the sandwich in every floor on the floor on the sandwich on the pickle on a floor with a president under the floor under every floor on a perplexed pickle on the president on a perplexed chief of staff on every delicious sandwich under a sandwich under every chief of staff in every floor on every perplexed pickle on a sandwich in every president with every sandwich under every sandwich under every chief of staff on the sandwich under a sandwich with every floor under a pickle with a sandwich in every chief of staff in the fine president on every sandwich with the pickle with every chief of staff with every pickled sandwich with the floor in a president with every perplexed floor in the floor under the pickled president in every president under a perplexed delicious delicious chief of staff under every sandwich under every pickle on the pickle under a perplexed president on a chief of staff in every chief of staff with every perplexed sandwich with every president under every president with every president with the fine perplexed president under every pickle under the sandwich with a president in a perplexed chief of staff with the floor with a fine pickle in a pickle on the pickle under a floor with every chief of staff with every president with a floor under the chief of staff with every sandwich under every fine pickle with the sandwich in the pickle with every pickle with every sandwich under the chief of staff in a floor under every chief of staff on the floor in the floor in the floor on a president on a president under a chief of staff with every sandwich in every sandwich on the sandwich on the pickle with every sandwich under a fine chief of staff in the chief of staff under every chief of staff in a pickle on a floor on every president on every sandwich in every sandwich on every floor in the pickle under the sandwich under a chief of staff on a sandwich on the floor with every president under a pickle with every sandwich in the pickle on every president under the fine floor with a chief of staff under the chief of staff under a floor with the fine perplexed president on every chief of staff on every chief of staff under every sandwich in the sandwich with a fine president on the floor with the president on the delicious floor in the chief of staff on the floor on the pickle with a sandwich under the sandwich in every fine floor in a sandwich in the pickle with every pickle in every pickled floor with the floor under a pickle under the chief of staff with the pickle on every delicious chief of staff on the sandwich with every floor under a sandwich on the pickle on a floor in every president with the president under a sandwich in every floor on the pickle with a pickle on a floor with every chief of staff with every president in a sandwich on the pickle under a floor with a president on the president under every delicious chief of staff under every pickle with a chief of staff in the floor with every pickle under the floor on every chief of staff in every perplexed pickle in the pickled president under every sandwich under every pickled chief of staff with every perplexed sandwich with the sandwich with the president with the president with a pickle on every chief of staff on every floor on every pickled sandwich under the president on a pickle in a chief of staff on a pickle with the perplexed chief of staff under a president under the perplexed president under every floor in a chief of staff with every sandwich with a chief of staff under a sandwich with every pickle in a sandwich on a president on every sandwich with every pickle under the pickled perplexed sandwich under a president in the pickle with the floor in the sandwich under the pickle under the pickle with every delicious chief of staff on every pickle under the floor under a president on every chief of staff with every pickle under a floor in every president with the perplexed president in every floor in every sandwich on a pickle with a delicious chief of staff under every floor under the floor under every sandwich on every delicious president with the sandwich on a chief of staff under the chief of staff in a president on a perplexed sandwich in a pickle under a fine pickle in a president with a chief of staff with every president in the chief of staff in every chief of staff with every floor on the pickle on a pickle in the sandwich with the floor under every sandwich on the perplexed chief of staff with a president on the chief of staff under the president in the pickle on every sandwich under the president in a sandwich in the floor on the chief of staff on the chief of staff in the sandwich on a chief of staff under every floor in the perplexed president under a sandwich under a chief of staff with the perplexed chief of staff with every perplexed president on the chief of staff on every pickled pickled chief of staff on the chief of staff with every chief of staff on every pickle under the pickle with the floor under the president under every delicious chief of staff with every sandwich on a floor in a pickle in the floor in every president under the chief of staff with every chief of staff under a pickle under every president on the pickle under every pickled floor on the floor on every chief of staff with a chief of staff with the floor on a chief of staff with the chief of staff on the chief of staff in the sandwich with the chief of staff under every delicious president on the pickled pickle under the delicious pickled fine fine sandwich on the chief of staff in the president in every chief of staff under every floor with a pickle in every chief of staff in every floor with every president under every president under a chief of staff on every fine chief of staff with a perplexed chief of staff in the pickle on a floor on the sandwich in a floor in a sandwich in every chief of staff in the sandwich under every delicious pickle with the delicious pickled president in a floor under the president under a pickle with the pickled floor on every fine fine chief of staff on the floor on a president in the chief of staff on every president under a sandwich with a sandwich with every floor under a chief of staff with a president under a chief of staff with the president on the chief of staff with the chief of staff on a sandwich under the president in every perplexed pickle under every pickle under a sandwich on the sandwich under every president under a pickled floor with every president under every chief of staff with every president on every floor in the sandwich on every pickle under every sandwich under every sandwich under a president with a pickle under a pickled pickle under the sandwich with every pickle in every floor with a pickle under every sandwich under the fine floor on every fine delicious chief of staff on a pickle in every pickle with a pickled pickle in the floor under the pickled president in the sandwich under the chief of staff on the pickle in every chief of staff in a floor in every pickle under a perplexed sandwich in a pickle on a president under every floor on a sandwich with a chief of staff on the pickle in the pickled delicious pickle in the floor in the pickled chief of staff in every chief of staff in a floor on the chief of staff under a president in the fine president with every president in every perplexed chief of staff with a floor in every pickle under the president with every pickle with a chief of staff with a chief of staff in the sandwich in every perplexed sandwich on a floor in every president on a pickle with a floor in every pickle with every sandwich in a chief of staff on every president with the sandwich with every sandwich on a president with every sandwich with the chief of staff with a floor under the chief of staff with the floor with every floor in the chief of staff with a president in every floor on the floor with every chief of staff under every pickle on a chief of staff on every pickle under every chief of staff with the floor in every president on a chief of staff in a chief of staff on the president under every chief of staff under a chief of staff in a sandwich with a president under the floor under the sandwich with a perplexed floor under a floor with every pickle under a sandwich in a delicious president under every president with a pickle with every president with a pickle with a pickle under the perplexed president in every sandwich with every chief of staff on every pickle in the chief of staff under the sandwich in the sandwich in a chief of staff with the sandwich with every pickled president on a perplexed floor in the president with every delicious pickle on every delicious pickled chief of staff on every chief of staff under a sandwich with every delicious pickle under every perplexed president with a pickle in a pickle under a pickle under the floor with every sandwich under the floor on the pickle on a chief of staff with every chief of staff under the sandwich with a pickle with every perplexed sandwich on a pickle on a perplexed president on the president in the floor in the sandwich on a pickle on every chief of staff in a chief of staff on a chief of staff under every pickle in every chief of staff with every pickle in the president under every president on every pickle in every floor with a floor in every pickle under a pickle on every president under every sandwich with every sandwich in a delicious pickle in every floor on the chief of staff on a floor on the president with a sandwich on a fine president on a pickle on a president under a sandwich under every sandwich in a president on every sandwich under the pickle on every floor on every president in a pickle under the delicious fine president on every pickled sandwich under a chief of staff on a president on every chief of staff in a sandwich on the pickle under a fine perplexed pickle under the sandwich with every president with the sandwich in every chief of staff with every delicious floor on the sandwich on a sandwich under every floor in a sandwich on every floor with a sandwich on every sandwich on a president under every sandwich in a sandwich with every floor under the perplexed pickle on every chief of staff in every sandwich with a chief of staff with the floor in the fine pickled chief of staff under a floor under every sandwich in every sandwich under a floor with a floor on every perplexed chief of staff under every sandwich with a chief of staff on every chief of staff in every pickled perplexed pickle on the pickle under the fine sandwich in a sandwich with the floor on the pickled fine president under every president with every pickle in the sandwich on the chief of staff in every president in every president in the president under every fine floor with the sandwich with a floor on a president on the sandwich under the sandwich with a sandwich on a floor in the fine sandwich in the pickle in every president on every sandwich under every sandwich in the perplexed chief of staff in every sandwich under the pickle on the pickle with the floor under every pickle in every chief of staff with every floor under every president with every pickle in every president on a chief of staff on a sandwich in a floor in the chief of staff under a pickle under a fine chief of staff on the chief of staff under every floor in every pickle in every floor under a floor with the chief of staff under the president on a fine delicious pickle with the chief of staff on every sandwich with a president under every pickled sandwich with every chief of staff in the perplexed floor with a pickle on the floor under the floor in every chief of staff under a floor on the chief of staff in every chief of staff in every pickle with the sandwich with a sandwich in every perplexed floor in a chief of staff in every floor in a pickle on a sandwich on the president in a pickle in a chief of staff with the floor on a president under every pickle on every delicious floor under every floor under every president with every delicious perplexed president under every sandwich with the floor in the president in every floor in the sandwich in the pickle under every president in every president under every chief of staff on the perplexed chief of staff with a sandwich under every chief of staff with the chief of staff on the floor under every floor on the president under a president in a sandwich with the floor with every pickle with every floor under every fine fine sandwich with every sandwich on every floor in every chief of staff with a floor under every floor with every sandwich with the floor on the sandwich with the fine sandwich with a sandwich under a pickle in every pickle on the sandwich with every pickle on every sandwich on the chief of staff with a floor with a president with the pickled chief of staff on the chief of staff on the chief of staff under a floor in every president under a president under every perplexed sandwich on every president under the president under the floor in every fine pickle with the chief of staff under a pickled chief of staff in a fine pickle under a chief of staff on the sandwich with the pickle in the pickle under a floor under every sandwich under the fine floor in every chief of staff on the floor on the chief of staff on a chief of staff in the president in the sandwich in every sandwich on the sandwich under the sandwich on a president with every chief of staff with the pickle under the president in every president with every floor with every president in every fine president in every floor in the sandwich on every chief of staff under every sandwich on a president with a floor under every floor on a floor under every chief of staff under the chief of staff in every sandwich under every pickle in the floor under the pickle under every chief of staff under the floor on the president with a fine pickle on the president in every fine pickle with every perplexed president on a floor in the delicious chief of staff in the chief of staff with the pickled president under the sandwich on every chief of staff with a chief of staff with a president on the floor on a floor in a chief of staff under every floor on every sandwich in the president with the president in a floor under the pickle in every floor on the delicious sandwich on the sandwich on every perplexed delicious president with a pickled sandwich in the sandwich under the chief of staff in a pickle in a fine pickle under the pickle on every floor in every pickle under every president under every chief of staff with every sandwich with the pickle in every chief of staff under every president under every president with a sandwich under every floor in every chief of staff in the chief of staff under a chief of staff on a chief of staff in every president on the president under every floor on a sandwich in the fine pickled floor in every floor under every sandwich under every president on a chief of staff under every pickle with the pickle on every perplexed chief of staff under a sandwich in the floor on the floor on a pickle on every chief of staff on a pickle with a president under a sandwich on a sandwich with a president on the chief of staff under every pickle on a floor in a fine pickle with a fine sandwich with a delicious chief of staff in a chief of staff on the pickle in every sandwich with the chief of staff on the sandwich under every floor with a perplexed delicious chief of staff with the floor under the president under every chief of staff in every sandwich with every floor on every floor with a chief of staff under a floor in the pickle under a sandwich under a chief of staff with a floor on a floor on every pickle under every floor under the chief of staff in every chief of staff on a president with every president on the president under every floor on every president with the pickle in every pickle in every pickle under the president on the sandwich on every sandwich on every president under a chief of staff with every pickle under a chief of staff on every chief of staff on the floor with the president in every president with every pickle on every sandwich in a perplexed pickle on every floor on every chief of staff on the chief of staff in a pickle with every chief of staff with a pickle under the fine pickle under the floor on the floor in the sandwich under the pickle with a chief of staff under the sandwich with a chief of staff with every floor on a fine pickle on the sandwich under the pickle under the pickle on a pickle with a floor with every floor with a floor in every pickle in the president on a sandwich with every floor under a perplexed chief of staff on the president with every fine sandwich on the pickle on every pickle with every delicious chief of staff with a sandwich on a pickle with every president on every perplexed floor on every sandwich on the sandwich under a floor on every perplexed chief of staff with a sandwich under every sandwich on the president in every chief of staff on every sandwich with the sandwich in the sandwich in the chief of staff with the pickle on a sandwich with a floor with a floor on every president in a chief of staff in a sandwich on every pickle on a pickle with every chief of staff in a chief of staff on a president in the floor under the president on the fine president with every pickled perplexed president with a chief of staff under every perplexed fine president under every pickle on the pickle on the sandwich with every chief of staff under the floor in a sandwich under the president on the fine floor under a pickle in a floor in every pickled pickle with a pickle with every perplexed sandwich with the sandwich on the perplexed chief of staff on a chief of staff under every president with a president with the pickle in every pickled sandwich on every floor with the pickle under the chief of staff in the floor under every pickle with a sandwich under every sandwich with every pickled pickled floor with every sandwich in every sandwich with a president in a sandwich on the perplexed floor with every perplexed president with every floor on the sandwich under the fine pickled chief of staff under the fine floor with a floor in the pickle under a pickle under the chief of staff under the floor with a fine pickled pickle with a chief of staff in every president under a chief of staff in a president in a perplexed floor on the president under a pickle under a floor under a sandwich on every president in the chief of staff on the sandwich with the sandwich in a perplexed sandwich on every sandwich on a floor on every pickle on a chief of staff in the president under a chief of staff with the floor in every perplexed president with a floor under every floor with a pickle under the president in a president in every pickle with a pickle on every pickled chief of staff on the floor in the president under a chief of staff on a president in every floor under the sandwich with the perplexed president with every floor with a floor with the president with the pickled pickle on a pickle with a president on the president in a sandwich on the chief of staff in the pickle with the president on a floor with a fine floor in the floor on a chief of staff with the president on every floor in a chief of staff on a floor with a floor on a president in the fine president in a sandwich in every floor with the president in the floor in the floor in a sandwich under a pickle under a chief of staff under every sandwich in the president on every sandwich on every president under a pickle in the pickle under the sandwich under every sandwich on the sandwich under every pickle on a floor with a floor with every chief of staff with every floor with every president on every fine pickled president under the president with a sandwich in the fine president with a floor on the delicious president with every chief of staff in a chief of staff with every chief of staff in every president under every perplexed president under every pickle under every sandwich in a president on a pickle under every perplexed pickle on the fine pickle on a pickle under the floor on every sandwich with a sandwich in a pickle with every chief of staff on the pickle with the floor with the sandwich on the pickled pickle with the pickle with the sandwich under the president on a sandwich on every delicious fine president on every chief of staff on a chief of staff with every sandwich on every pickle on every fine sandwich with the sandwich in a pickled chief of staff under every president with the floor under every chief of staff under a president on the president with the pickle on the chief of staff on a floor under every pickle with every chief of staff in every perplexed pickled floor in a perplexed pickle with a chief of staff with a floor under a sandwich with a sandwich in a perplexed president in the pickle with the pickle with a pickle under the floor in a floor on every chief of staff under the chief of staff with a president in every president on a pickle under the pickle on the pickle in a sandwich under a president under the pickle on every pickle on the fine perplexed chief of staff on every floor on the pickle with the sandwich on a chief of staff on a perplexed floor in the delicious sandwich in a president in a pickle under every delicious chief of staff with every floor in a pickle in every floor on the fine floor in a sandwich with the floor under every floor in every floor with a delicious perplexed sandwich in every chief of staff with every sandwich on every delicious sandwich in the floor under every president on every chief of staff in every pickle in every pickled chief of staff in a president in a pickle on a floor with a pickled chief of staff in every sandwich with a pickled pickle under the chief of staff on the president in the president under a floor with a sandwich in every president with the delicious chief of staff on every sandwich on a chief of staff with the sandwich in a perplexed sandwich under every chief of staff on a pickle in a pickle under the perplexed chief of staff on a floor with a perplexed pickle with the sandwich with the chief of staff on every floor in the pickled floor in a sandwich in the president under a pickle in the floor with a sandwich in a president in every chief of staff under the chief of staff with the president with every sandwich with the floor with every chief of staff in the chief of staff under the sandwich under every sandwich under a delicious pickled chief of staff under a sandwich on the chief of staff with the pickle under a chief of staff in the delicious president under the sandwich under every floor under the perplexed fine president on the chief of staff with every floor on the floor with every chief of staff in a pickle in a president with the chief of staff on the sandwich with a sandwich under every floor under a sandwich in every chief of staff with a pickled pickle with a pickled chief of staff under every pickle with the chief of staff with a sandwich on the chief of staff in the president on every chief of staff in the chief of staff with a floor in the pickle under a pickle in the sandwich under a perplexed president under every floor on the chief of staff in the floor under the president under every sandwich with a delicious pickled floor in every floor with a floor on a pickled chief of staff with every president in a chief of staff under every chief of staff with the delicious fine pickle on a floor under every floor on a floor with the president in a pickle in every floor in every pickle on the fine chief of staff with the floor on a president on a sandwich with the sandwich on every fine chief of staff under every pickle under the sandwich in the pickle under every delicious floor on the chief of staff on every chief of staff under a pickle with a floor on the chief of staff in a pickle on every floor with a sandwich in every fine floor under every floor under the president in a sandwich under every floor in every perplexed perplexed floor on the chief of staff with every pickle under every president on a pickle under every pickle in a sandwich on a perplexed floor in a sandwich in a chief of staff with a president in every sandwich on the floor on a sandwich on a sandwich under a pickle on a chief of staff in the president with the chief of staff in every perplexed sandwich under a chief of staff in every delicious sandwich in the pickle on every delicious president under every pickle in the chief of staff on the pickle under the president with every president in the sandwich on every perplexed sandwich on every sandwich in the sandwich on the delicious floor in the floor in a chief of staff with every president with a pickle on every perplexed delicious floor under the floor under every president on every fine fine pickle on the chief of staff with every floor under every sandwich on every fine floor on every president on a fine delicious floor on a chief of staff under every president in a floor in a floor with the chief of staff with the floor with a floor on a sandwich under a pickle under every floor under every pickle under every chief of staff under the chief of staff with every chief of staff in the chief of staff under a pickle on every floor on every sandwich under the pickle under every sandwich with a pickle in a sandwich under the perplexed sandwich with the floor on the pickle in every chief of staff in a president under a chief of staff under the floor under a delicious sandwich with a president under the sandwich under a fine chief of staff under a president under every president on a chief of staff on every president on a pickle under every president in every president in the president in every pickle with every chief of staff with a pickled floor on the president under a sandwich under every floor on a president under every chief of staff on every perplexed floor on the perplexed floor on a pickle under the chief of staff under every sandwich with a sandwich with the floor under the pickle on the delicious pickle on the president under a president in a chief of staff under the delicious pickle under a president under every pickle under every delicious pickle under every pickled floor under every pickle with the sandwich on the chief of staff understood the president .

every delicious president with the floor ate every pickle .

the president in every pickle in the chief of staff in the pickle understood the pickled floor on a president on a pickle under every pickle in a perplexed president in every president !

a floor ate every fine pickle .

every pickle ate the floor !

is it true that every perplexed president on the delicious sandwich understood every chief of staff ?

every pickle pickled the president . 
\end{itshape}

\item\begin{enumerate}
\item {\bf Why does your program generate so many long sentences?}
    Specifically, what grammar rule is responsible and why? What is
    special about this rule?

The grammar rule:

  NP = NP PP

is responsible for that. The special thing of this rule is that it's recursive, and the
probability of choosing it is large (compared to another recursive rule: ``Noun = Adj Noun'').

\item The grammar allows multiple adjectives, as in, \verb|the fine perplexed pickle|. 
{\bf Why do your generated program's sentences exhibit this so rarely?}

Because there are other 5 rules with Noun as LHS competing with the recursive rule generating
this multiplicity of adjectives, namely ``Noun = Adj Noun''.

\item {\bf Which numbers must you modify to fix the problems in 2(a) and
    2(b), making the sentences shorter and the adjectives more
    frequent? (Check your answer by running your new generator and
    show that they work.)}

The number before the rule ``NP = NP PP'' and the number before the rule ``Noun = Adj Noun''.
I changed the former to 0.1 and latter to 5, and now sentences are like these:

\begin{itshape}
a perplexed pickled president understood every delicious perplexed president !

every pickle pickled every president .

every fine sandwich kissed a floor !

is it true that a delicious fine sandwich kissed a fine perplexed perplexed perplexed president ?

the fine perplexed pickled pickle wanted the delicious president !

a sandwich ate every president with every perplexed delicious pickled delicious floor !

the president pickled every president .

every fine perplexed president ate a fine fine fine floor .

every president pickled a sandwich .

is it true that every pickled fine president pickled a delicious perplexed perplexed perplexed chief of staff ?
\end{itshape}

\item {\bf What other numeric adjustments can you make to the grammar in
  order to favor more natural sets of sentences? Experiment. Hand in
  your grammar file as a file named \verb+grammar2+, with comments that
  motivate your changes, together with 10 sentences generated by the
  grammar.}

I changed the number for Rule ``Noun = Adj Noun'' down to 1.5 because multiple adjectives
are not very common.

10 example sentences:

\begin{itshape}
a delicious delicious floor pickled a perplexed chief of staff .

is it true that every pickle ate a floor ?

is it true that a chief of staff understood the floor ?

is it true that every floor kissed every president ?

is it true that a chief of staff pickled the chief of staff ?

is it true that a floor with every floor ate the president ?

every chief of staff in every fine president understood every chief of staff !

a chief of staff ate every sandwich !

a fine pickle under every chief of staff pickled the fine chief of staff !

is it true that a chief of staff understood the delicious fine pickle ?
\end{itshape}

\end{enumerate}
\item {\bf Modify the grammar into a new single grammar that can also generate the types of
  phenomena illustrated in the following sentences.}
\begin{enumerate}
\item \verb| Sally ate a sandwich .|
\item \verb| Sally and the president wanted and ate a sandwich .|
\item \verb| the president sighed .|
\item \verb| the president thought that a sandwich sighed .|
\item \verb| that a sandwich ate Sally perplexed the president .|
\item \verb| the very very very perplexed president ate a sandwich .|
\item \verb| the president worked on every proposal on the desk .|
\end{enumerate}

\noindent
{\bf Briefly discuss your modifications to the grammar. Hand
  in the new grammar (commented) as a file named \verb|grammar3| and about 10
  random sentences that illustrate your modifications.}

For (b), I added conjuncation structures to VP and NP.
An easy way to do that is like ``VP = VP Conj VP'', but it leads to ambiguous grammar, and 
I'm not sure whether three or more conjuncts are grammatical. So I limited the number of 
conjuncts to two by using ``VPs''(single VP) to represent each conjunct. 

For (c), I added intransitive verbs (Vi). 

For (d), I added noun clauses. But noun clauses do not behave exactly as a NP. For one thing,
noun clauses cannot be motified by PP. For another, a noun clause cannot be preceded by a
Prep to form a PP. So I introduced the notion of ``NPnc''(non-clause NP) to enforce those 
constraints. 

For (f), I added adverbs and adverb phrases. If there are multiple adverbs, are those adverbs
modifying the common adjective, or the preceding adverb is modifying the following adverb?
My grammar teacher taught me the latter case is legal, i.e., adverbs can modify adverbs, as 
in ``He runs extremely slowly''. So I picked the latter case.  

For (g), I enabled a Vi to be followed by a PP.

\item {\bf Give your program an option ``\verb|-t|'' that makes it produce
  trees instead of strings. Generate about 5 more random
sentences, in tree format. Submit them as well as the commented code
for your program.} 

5 examples:

\begin{verbatim}

(START (ROOT (S (NP (NP (Det (the ))
                        (Noun (Adj (fine ))
                              (Noun (Adj (perplexed ))
                                    (Noun (president )))))
                    (PP (Prep (under ))
                        (NP (Det (a ))
                            (Noun (sandwich )))))
                (VP (Verb (wanted ))
                    (NP (Det (the ))
                        (Noun (president )))))
             (. )))

(START (ROOT (S (NP (Det (the ))
                    (Noun (chief )
                          (of )
                          (staff )))
                (VP (Verb (ate ))
                    (NP (Det (a ))
                        (Noun (floor )))))
             (! )))

(START (ROOT (S (NP (Det (every ))
                    (Noun (floor )))
                (VP (Verb (wanted ))
                    (NP (Det (a ))
                        (Noun (floor )))))
             (! )))

(START (ROOT (S (NP (Det (every ))
                    (Noun (president )))
                (VP (Verb (understood ))
                    (NP (Det (the ))
                        (Noun (Adj (delicious ))
                              (Noun (president ))))))
             (. )))

(START (ROOT (S (NP (Det (every ))
                    (Noun (Adj (delicious ))
                          (Noun (pickle ))))
                (VP (Verb (understood ))
                    (NP (Det (the ))
                        (Noun (Adj (delicious ))
                              (Noun (pickle ))))))
             (! )))

\end{verbatim}

\item When I ran my sentence generator on \verb|grammar|, it produced
  the sentence:
\begin{verbatim}
every sandwich with a pickle on the floor wanted a president .
\end{verbatim}
\noindent
This sentence is ambiguous according to the grammar, because it could
have been derived in either of two ways.
\begin{enumerate}
\item  One derivation is as follows; {\bf what is the other one?}

\bigskip
\begin{verbatim}
(START (ROOT (S (NP (NP (NP (Det every)
                            (Noun sandwich))
                        (PP (Prep with)
                            (NP (Det a)
                                (Noun pickle))))
                    (PP (Prep on)
                        (NP (Det the)
                            (Noun floor))))
                (VP (Verb wanted)
                    (NP (Det a)
                        (Noun president))))
             .))
\end{verbatim}

The other one is:

\begin{verbatim}
(START (ROOT (S (NP (NP (Det every)
                        (Noun sandwich))
                    (PP (Prep with)
                        (NP (NP (Det a)
                                (Noun pickle))
                            (PP (Prep on)
                                (NP (Det the)
                                    (Noun floor))))))
                (VP (Verb wanted)
                    (NP (Det a)
                        (Noun president))))
             .))
\end{verbatim}


\item {\bf Is there any reason to care which derivation was used?}

Yes. For the first one, the sandwich is on the floor. For the second one, the pickle is 
on the floor. So meanings are different.

\end{enumerate}

\item\begin{enumerate}
 \item {\bf Does the parser
  always recover the original derivation that was ``intended'' by
  \verb|randsent|? Or does it ever ``misunderstand'' by finding an alternative
  derivation instead?  Discuss. (This is the only part of question 6a
  that you need to answer.)}

Yes. Here is one:

\begin{verbatim}
(START (ROOT (S (NP (NP (NP (Det every)
                            (Noun sandwich))
                        (PP (Prep on)
                            (NP (Det the)
                                (Noun pickle))))
                    (PP (Prep under)
                        (NP (Det every)
                            (Noun (Adj pickled)
                                  (Noun floor)))))
                (VP (Verb pickled)
                    (NP (Det the)
                        (Noun (Adj fine)
                              (Noun (Adj delicious)
                                    (Noun floor))))))
             !))
\end{verbatim}

I could have meant that the pickle is on the floor. But here it means the sandwich is on
the floor. In grammar2 the only source of ambiguity seems come from the multiple PPs.

\item {\bf How many ways are there to analyze the following Noun Phrase (NP)
  under the original grammar?  Explain your answer.}

There are 5 ways in total. To prove it, let's observe first that there are 3 PPs. All the 
possible hierarchies among these 5 PPs can be expressed like this:

\begin{verbatim}
(NP (PP) 
    (PP) 
    (PP))

(NP (PP (...)
        (PP)) 
    (PP))

(NP (PP) 
    (PP (...)
        (PP)))

(NP (PP (...)
        (PP)
        (PP)))

(NP (PP (...)
        (PP (...)
            (PP))))
\end{verbatim}

That is, all 3 PPs can be on the same level (1 option), or 2 of them can be on the higher 
level (2 options), or 1 of them can be on the highest level (2 options). Qed.

When I use this command to check my answer:

\begin{verbatim}
echo "every sandwich with a pickle on the floor under the chief of staff 
ate a pickle ." | ./parse -g grammar -c
\end{verbatim}

The parser answers ``\verb|no._parses= 5|''.

\item By mixing and matching the commands above, generate a bunch of
  sentences from \verb|grammar|, and find out how many different parses they
  have. Some sentences will have more parses than others. {\bf Do you
  notice any patterns? Try the same exercise with \verb|grammar3|.}

Yes. The number of parse trees is determined by the number of PPs in the sentence. The more 
PPs, the more parse trees. Grammar3 has much less ambiguous sentences, because the probability
of generating multi-PP sentences in Grammar3 is much reduced.

\begin{enumerate} 
\item {\bf Probability analysis of first sentence: Why is \verb|p(best_parse)| so small?  What probabilities were
  multiplied together to get its value of 5.144032922e-05?}\\
\noindent
\verb|p(sentence)| is the probability that \verb|randsent| would
  generate this sentence. {\bf Why is it equal to \verb|p(best_parse)|?}\\
\noindent
{\bf Why is \verb+p(best_parse|sentence)+=1?}

It's small because it's the product of many probabilities.  They are:

\begin{verbatim}
p(Root->S .)=1/3
p(NP->Det Noun)=1/2
p(Det->the)=1/3
p(Noun->president)=1/6
p(Verb->ate)=1/5
p(Det->the)=1/3
p(Noun->sandwich)=1/6
p(NP->Det Noun)=1/2
\end{verbatim}

and some other 1s.

It's equal to \verb|p(best_parse)| because there are only one parse. That's also the reason 
why \verb+p(best_parse|sentence)+. Actually, \verb+p(sentence)+ is defined as:

$$p(\mathrm{sentence})=\sum_n p(\mathrm{parse}_n)$$

\item {\bf Probability analysis of the second sentence:  \\
\noindent
What does it mean that \verb+p(best_parse|sentence)+ is 0.5 in this
case? \\
\noindent
Why would it be {\it exactly} 0.5?}

It means that the probability of the best parse takes up a half of the probability of all
possible parses. It's 0.5 because there are 2 possible parses, and they are of equal 
probability (because the grammar sets all the numbers to 1).

\item {\bf Cross-entropy of the two sentence corpus. Explain exactly
    how the following numbers below were calculated from the two sets
    of numbers above, that is, from the parse of each of the two
    sentences.}

The cross-entropy is calculated as:

$$
H=-1/18*(\log_2(5.144032922e-05)+\log_2(1.240362877e-09))=2.435185067
$$
 
The number of bits is calculated as:

$$
B=-(\log_2(5.144032922e-05)+\log_2(1.240362877e-09))=43.8333312
$$

\item {\bf Based on the above numbers, what {\it perplexity} per word did
  the grammar achieve on this corpus?}

$$\mathrm{perplexity}=2^H=5.40833706051154$$

\item {\bf The compression program might not be able to compress the
    following corpus that consists of just two sentences very well.
    Why not? What cross-entropy does the grammar achieve this time?
    Try it and explain.}  (The new 2 sentence corpus is given below.)

This time the cross-entropy goes to infinity. That's because the grammar cannot generate
the second sentence (ate in the grammar is a transitive verb), so its probability is 0.

\item {\bf How well does {\tt grammar2} do on average at predicting
    word sequences that it generated itself?  Please provide an answer
    in bits per word.  State the command (a Unix pipe) that you used
    to compute your answer.}

The command I used is:

\verb+python randsent.py grammar2 100 | ./parse -C -g grammar2+

The entropy for grammar2 is about 1.8, and that for grammar3 is about 2.4 .
Grammar3 can generate a wider variety of sentences than grammar2.

I tried to use 5 sentences generated from grammar1 to calculate entropy. When it succeeds,
the entropy is about 2. But often it takes too long because the sentences are too long.

\item If you generate a corpus from {\tt grammar2}, then {\tt
    grammar2} should on average predict this corpus better than {\tt
    grammar} or {\tt grammar3} would. In other words, the entropy will
  be {\it lower} than the cross-entropies. {\bf Check whether this is true:
    compute the numbers and discuss.} 

The entropy of grammar2 is about 1.8. The cross-entropy using grammar to parse is about
2.0. The cross-entropy using grammar3 is about 2.6. Both cross-entropies are lower than
grammar2's entropy.

Grammar is closer to grammar2, so its
number is lower than grammar3's. Grammar3 is relatively further from grammar2.

\end{enumerate}
\end{enumerate}

\item  {\bf Think about all of the following phenomena, and extend your grammar
  from question 3 to handle them. (Be sure to handle the particular
  examples suggested.)  Call your resulting grammar
  \verb|grammar4| and be sure to include it in your write-up along with examples of it
  in action on new sentences like the ones illustrated below.}

\begin{enumerate}
Here are 10 examples generated from my grammar4:

\begin{itshape}
who worked ?

did that every delicious perplexed chief of staff and the very fine desk signed work with the desk ?

who did the proposal and every sandwich work under ?

who will the floor understand that signed with the very very pickled delicious pickle ?

what will every proposal or a desk think the perplexed perplexed very very very very perplexed president under ?

who did every perplexed Sally think every proposal and every delicious sandwich with ?

what worked or worked on the floor ?

who did the delicious fine delicious pickled sandwich in a Sally sign with ?

who will the president or every sandwich pickle ?

what will every president sign on ?
\end{itshape}

\item {\it Yes-no questions}.

For these examples, firstly we need a set of verbs in their original forms. Then we need 
auxiliary verbs (e.g. did, will). Then the rule to generate these examples will be like
``S = AuxV NP VPo'', where VPo differs from VP only in that it uses the original form for
its main verb insteal of past tense. To achieve this, we need to actually copy the rules
involving VP and make a original-form version.

\item {\it WH-word questions.} 

The first 3 examples are questions asking about a non-subject part of the sentence. Its 
format can be described as a noun WH-word (e.g. what, who) followed by a auxiliary verb 
follow by a sentence with the asked part missing (the sentence should use original-form
verb as its main verb). I express this missing part as a ``hole''. So basically what I did
is to use rules to dig a ``hole'' in a sentence. A ``hole'' can be a 
missing object, or trickier, a missing noun deep inside a clause or a prepositional phrase
(as in example 2 and example 3 correspondingly). The way to use rules to dig a ``hole'' is 
to label some nonterminals to be ``with a hole'', and propagate this label from high-level
nonterminals to low-level nonterminals. At some level, a rule may decide that it is proper 
to put the ``hole'' here, achieved by deleting a part in the RHS. For example in the rule
``PPh = Prep'' (suffix ``h'' stands for ``hole''), the NP is deleted from the original rule ``PP = Prep NP'', thus digging
a ``hole'' here. Or a rule may choose to not dig the ``hole'' here, but instead to pass
the ``hole'' label down, as what the rule ``VPh = Verb NPh'' does. 

Example 4 is a question asking about the subject of a sentence. It's easy to be dealt with. Just replace
the subject of a normal sentence with a noun Wh-word.

Example 5 is a WH-question using an adverb WH-word (e.g. where, when). It's also easy. Just
put an adverb WH-word in front of Yes-No question.

\end{enumerate}
\end{enumerate}
\end{document}

